#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <time.h>
#include <unordered_map>
#include <tspSolution.hpp>
#include <tspLoad.hpp>
using namespace std;

#define ADAPT_RATIO 0.01
#define OUTPUT_FREQUENCY 50
#define OUTPUT_ONLY_NEW_SOLUTION_FOUND 0
#define MUTATION_PERCENTAGE 0.01
#define INIT_ROUTE_CNT 100

// 城市结构体方法补全
city::city(double posX, double posY, string name) {
    this->posX = posX;
    this->posY = posY;
    this->name = name;
}

// 路线结构体方法补全
route::route(vector<city> cities) {
    this->cities.assign(cities.begin(), cities.end());
}

void route::randomize() {
    random_shuffle(cities.begin(), cities.end());
}

void route::swap(int swapIndex1, int swapIndex2) {
    city swapTemp = cities[swapIndex1];
    cities[swapIndex1] = cities[swapIndex2];
    cities[swapIndex2] = swapTemp;
}

double route::returnRouteLength() {
    double result = 0;
    for (int i = 0; i <= cities.size() - 1; i++) {
        result += returnDistance(cities[i % cities.size()],
            cities[(i + 1) % cities.size()]);
    }
    return result;
}

double route::getAdaptability(const double ratio) {
    return exp(-abs(ratio) * returnRouteLength());
}

// 结果结构体方法补全
result::result() {
    this->distance = __DBL_MAX__;
    // 初始化一个虚拟解，这个解比任何一个解都差
}

string result::returnAsFinalOutput() {
    string result = "The Final Solution >> The Distance Of The Final Solution Is " + to_string(distance);
    result += "\nThe Route Was : \n";
    for (int i = 0; i <= cities.size(); i++) {
        result += "City " + to_string(i) + " >> " + cities[i % cities.size()].name + "\n";
    }
    return result;
}

string result::returnResultOutput(int round) {
    string result = "Round " + to_string(round) +
        " : The Distance Of Current Solution Is " + to_string(distance);
    return result;
}

// 算法操作

/// @brief 对某条路线执行变异操作
/// @param currRoute 当前路线
/// @param percentage 可能性
void tryMutation(route& currRoute, const double percentage) {
    double potential = (double)rand() / RAND_MAX;
    if (potential <= percentage) {
        int swapIndex1 = rand() % currRoute.cities.size();
        int swapIndex2 = rand() % currRoute.cities.size();
        currRoute.swap(swapIndex1, swapIndex2);
    }
}

/// @brief 对两条线路实施杂交操作，杂交操作为位置杂交（PF），
/// @brief 我们除了片段互换，还关心城市在互换片段中的相对位置
void doCrossOver(route& route1, route& route2) {
    int cutIndex = rand() % (route1.cities.size() - 1);
    int left, right;
    if (rand() & 1) { left = 0; right = cutIndex; }
    else { left = cutIndex + 1; right = route1.cities.size() - 1; }
    // 现在，我们要交换的片段为[left, right]
    vector<city> newRoute1(route1.cities);
    vector<city> newRoute2(route2.cities);
    // 创建两个数组的深拷贝
    copy(route1.cities.begin() + left, route1.cities.begin() + right + 1,
        newRoute2.begin() + left);
    copy(route2.cities.begin() + left, route2.cities.begin() + right + 1,
        newRoute1.begin() + left);
    // 交换指定片段
    unordered_map<string, int> route1Map;
    for (int i = left; i <= right; i++) { route1Map.insert(pair<string, int>(newRoute1[i].name, 1)); }
    unordered_map<string, int> route2Map;
    for (int i = left; i <= right; i++) { route2Map.insert(pair<string, int>(newRoute2[i].name, 1)); }
    // 创建哈希表记录交换片段中的城市，防止在创建新片段时城市重复
    int originPtr = 0;
    for (int i = 0; i < newRoute1.size(); i++) {
        if (!(i >= left && i <= right)) {
            if (route1Map.find(newRoute1[i].name) != route1Map.end()) {
                // 这是个重复城市！
                while (route1Map.find(route1.cities[originPtr].name) != route1Map.end()) { originPtr++; }
                newRoute1[i] = route1.cities[originPtr++];
            }
            route1Map[newRoute1[i].name] = 1;
        }
    }
    originPtr = 0;
    for (int i = 0; i < newRoute2.size(); i++) {
        if (!(i >= left && i <= right)) {
            if (route2Map.find(newRoute2[i].name) != route2Map.end()) {
                // 这是个重复城市！
                while (route2Map.find(route2.cities[originPtr].name) != route2Map.end()) { originPtr++; }
                newRoute2[i] = route2.cities[originPtr++];
            }
            route2Map[newRoute2[i].name] = 1;
        }
    }
    // 处理重复城市的问题，生成新的城市，并保持其在自己原先状态中的相对顺序
    route1.cities = newRoute1;
    route2.cities = newRoute2;
    // 生成新的路线替代原先的route
}

/// @brief 获取两个城市之间的距离
double returnDistance(const city& city1, const city& city2) {
    return hypot(abs(city1.posX - city2.posX), abs(city1.posY - city2.posY));
}

/// @brief 生成初始的路线种群
/// @param cities 城市列表
/// @param routeCnt 路线数目
/// @return 一个包含指定数目的随机路线列表
vector<route> initalize(const vector<city>& cities, const int routeCnt) {
    vector<route> routes;
    srand((unsigned)time(NULL));
    for (int i = 0; i < routeCnt; i++) {
        route newRoute(cities);
        newRoute.randomize();
        routes.push_back(newRoute);
    }
    return routes;
}

/// @brief 返回当前回合时最优解
/// @return 一个结果结构体，包含路线和距离信息
result returnCurrSolution(vector<route>& routes) {
    result answer;
    for (route currRoute : routes) {
        double currDist = currRoute.returnRouteLength();
        if (currDist < answer.distance) {
            answer.cities = vector<city>(currRoute.cities);
            answer.distance = currDist;
            // 这个状态的解更好!
        }
    }
    return answer;
}

/// @brief 根据路线适应度选择（轮盘法）一条路线
/// @return 指定路线的下标
int chooseRoute(vector<route>& routes) {
    double adaptabilitySum = 0;
    for (route currRoute : routes) { adaptabilitySum += currRoute.getAdaptability(ADAPT_RATIO); }
    double counter = ((double)rand() / RAND_MAX) * adaptabilitySum;
    double currCounter = 0;
    for (int i = 0; i < routes.size(); i++) {
        currCounter += (routes[i]).getAdaptability(ADAPT_RATIO);
        if (currCounter >= counter) { return i; }
    }
    return routes.size() - 1;
}

/// @brief 返回TSP问题的一个可能解
/// @return 一个route结构体，包含当前路线信息
/// @param roundLimit 该算法的最大执行回合数
/// @param freezeLimit 答案保持不变的最大容忍回合数
result returnPossibleSolution(vector<city>& cities, const int activeLimit, const int freezeLimit) {
    vector<route> routes = initalize(cities, INIT_ROUTE_CNT);
    result answer;
    int count = 0, currFreezeRound = 0;
    while (count <= activeLimit && currFreezeRound <= freezeLimit) {
        result currResult = returnCurrSolution(routes);
        if (currResult.distance < answer.distance) {
            // 这个状态的解更好!
            currFreezeRound = 0;
            answer = currResult;
            if (OUTPUT_ONLY_NEW_SOLUTION_FOUND)
                cout << answer.returnResultOutput(count) << endl;
        }
        // 杂交两条路线
        doCrossOver(routes[chooseRoute(routes)], routes[chooseRoute(routes)]);
        for (route currRoute : routes) {
            tryMutation(currRoute, MUTATION_PERCENTAGE);
        }
        if (!(count % OUTPUT_FREQUENCY) && !OUTPUT_ONLY_NEW_SOLUTION_FOUND) {
            cout << answer.returnResultOutput(count) << endl;
        }
        count++; currFreezeRound++;
    }
    return answer;
}